package jam4j.util;

/**
 * A routine for matching shell-style globs, as defined by Jam.
 * 
 * @author Luke Maurer
 */
public abstract class Globs {
    // This lets us short-circuit suffix matches
    private enum Verdict { MATCH, NO_MATCH, TOO_LONG }

    private Globs() { }

    /**
     * Find whether the given filename matches the given glob. The glob may
     * use the standard {@code *}, {@code ?}, and {@code []} constructs;
     * backslashes escape.
     * 
     * @param filename The filename to match.
     * @param glob The glob to match against.
     * @return Whether the given filename matches the given glob.
     */
    public static boolean matches(String filename, String glob) {
        return verdict(filename, glob) == Verdict.MATCH;
    }

    private static Verdict verdict(String filename, String glob) {
        final int nameLen = filename.length(), globLen = glob.length();
        int nameIx = 0, globIx = 0;
    
        while (true) {
            if (globIx == globLen)
                return nameIx == nameLen ?
                    Verdict.MATCH : Verdict.TOO_LONG;
    
            char c;
            switch (c = glob.charAt(globIx++)) {
                case '?':
                    if (nameIx++ == nameLen)
                        return Verdict.NO_MATCH;
                    break;
                case '*':
                    if (globIx == globLen)
                        // Glob ends with *
                        return Verdict.MATCH;
                    
                    // Now we determine whether some suffix of the filename
                    // matches the remainder of the glob
                    for (int suffixIx = nameLen; suffixIx > nameIx;
                            suffixIx--) {
                        switch (verdict(
                                    filename.substring(suffixIx),
                                    glob.substring(globIx))) {
                            case MATCH:
                                return Verdict.MATCH;
                            case TOO_LONG:
                                // If that suffix doesn't match because
                                // it's too long, taking a bigger suffix won't
                                // help any
                                return Verdict.NO_MATCH;
                            default:
                        }
                    }
                    // Match zero characters
                    break;
                case '[': {
                    if (nameIx == nameLen)
                        return Verdict.NO_MATCH;
    
                    final int endIx;
                    if ((endIx = glob.indexOf(']', globIx + 1)) == -1)
                        // Play nice, like jam; invalid globs just don't
                        // match anything
                        return Verdict.NO_MATCH;
                    
                    final boolean negative = glob.charAt(globIx) == '^';
                    final String chars = glob.substring(
                            negative ? globIx + 1 : globIx, endIx);
    
                    if (negative == (chars.indexOf(
                                    filename.charAt(nameIx++)) == -1))
                        return Verdict.NO_MATCH;
    
                    globIx = endIx + 1;
                    break;
                }
                case '\\':
                    if (globIx == globLen)
                        // Invalid
                        return Verdict.NO_MATCH;
    
                    // Match next character of glob literally
                    c = glob.charAt(globIx++);
                    // Fall through
                default:
                    if (nameIx == nameLen || c != filename.charAt(nameIx++))
                        return Verdict.NO_MATCH;
            }
        }
    }
}
